Khalid dilahirkan c. 592 di Makkah, anak kepada Walid bin al-Mughira, ketua Bani Makhzum, sebuah suku daripada suku bangsa Quraisy. Bani Makhzum satu daripada tiga suku yang terunggul di Makkah pada masa itu – yang dua lain ialah Bani Hasyim dan Banu Abdul Dar (Bani Abd-al-dar). Beliau sepupu Saidina Umar. Bapanya terkenal di Makkah dengan gelaran Al-Waheed (Yang Satu).[2] Bani Makhzum bertanggungjawab tentang perkara-perkara berkaitan dengan peperangan. Sejurus selepas kelahirannya, dan dengan mengikut resam orang Quraisy, Khalid dihantar untuk tinggal bersama suku kaum Badwi di kawasan gurun Arabia, dan disusukan oleh seorang ibu susu yang juga membesarkan kanak-kanak dalam suasana persekitaran udara padang pasir yang kering, nyaman dan bersih. Beliau pulang kepada ibu bapanya semasa berumur lima atau enam tahun. Semasa zaman kanak-kanak, Khalid diserang penyakit cacar; beliau pulih akan tetapi penyakit cacar itu meninggalkan parut pada pipi kirinya.[3]

Khalid dan Umar, Khalifah kedua, sepupu dan wajah mereka mirip masing-masing. Mereka tinggi dan Khalid juga berbadan tegap dan berbahu lebar. Beliau berjanggut tebal.[4] Beliau juga seorang juara gusti.

Sebagai seorang ahli Bani Makhzum, satu suku yang pakar dalam peperangan dan dikira antara penunggan kuda yang terbaik di Semenanjung Arab, pada zaman kanak-kanaknya, Khalid belajar menunggang kuda dan mengguna senjata seperti tombak, lembing, busur dan pedang. Dikatakan tombak menjadi senjata kesukaannya. Pada zaman remaja beliau disanjung sebagai seorang pahlawan dan ahli gusti oleh orang Quraisy.[5]